package simple.array.sort;

/**
 * <a href="https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits">1356. 根据数字二进制下 1 的数目排序</a>
 * 给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
 * 如果存在多个数字二进制中1的数目相同，则必须将它们按照数值大小升序排列。
 * 请你返回排序后的数组。
 * @author 刘学松
 * @date 2021-02-02 23:06
 */
public class 根据数字二进制下1的数目排序 {
    public static void main(String[] args) {
        int[] arr = {1024,512,256,128,64,32,16,8,4,2,1};
        for (int i : sortByBits(arr)) {
            System.out.println(i);
        }
    }

    public static int[] sortByBits(int[] arr) {
        int[] array = new int[arr.length];
        int[] sortArr = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            array[i] = countBits(arr[i]);
        }
        for (int i = 0; i < array.length; i++) {
            // 找array中最小数的下标
            int minNumIndex = 0;
            for (int j = 1; j < array.length; j++) {
                if (array[minNumIndex] > array[j] || (array[minNumIndex] == array[j] && arr[minNumIndex]>arr[j])) {
                    minNumIndex = j;
                }
            }
            array[minNumIndex] = 33;
            sortArr[i] = arr[minNumIndex];
        }

        return sortArr;
    }

    public static int countBits(int num) {
        int count = 0;
        while(num != 0) {
            num= num & (num-1);
            count++;
        }
        return count;
    }
}
